package daily.year2024.m10;

/**
 * 201.数字范围按位与
 *
 * @author wjs 2024/10/21
 */
public class d21 {
    //解法一：找到左右边界的公共前缀
    //属于思维转换类型的题目
    class Solution1 {
        public int rangeBitwiseAnd(int left, int right) {
            int cnt = 0;
            while(left != right) {
                left = left >>> 1;
                right = right >>> 1;
                cnt++;
            }
            return left << cnt;
        }
    }

    //解法二：Brian Kernighan 算法
    //使用消除低位1的方法，直到right <= left
    //属于解法一的优化版本
    class Solution2 {
        public int rangeBitwiseAnd(int left, int right) {
            while(left < right) {
                right = right & (right - 1);
            }
            return right;
        }
    }
}
